package com.njupt.LinkTable;

import lombok.val;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/4/15 21:58
 * @Description: 146. LRU 缓存
 * @Version: 1.0
 */


public class LRUCache_146 {





    class DLinkedNode{

        public int key;

        public int value;

        public DLinkedNode pre;

        public DLinkedNode next;

        public DLinkedNode(int key,int value){
            this.key = key;
            this.value = value;
        }

        public DLinkedNode(){}

    }


    public DLinkedNode head;

    public DLinkedNode tail;

    private int capacity;

    private int size;

    Map<Integer,DLinkedNode> cache = new HashMap<Integer,DLinkedNode>();




    public LRUCache_146(int capacity) {
        this.capacity = capacity;
        this.head = new DLinkedNode(-1,-1);
        this.tail = new DLinkedNode(-2,-2);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        
        //1、从hash表中快快速定位到该节点在双向链表的哪个位置
        
        //1.1、不存在直接返回-1
        DLinkedNode node = cache.get(key);
        if(node == null){
            return -1;
        }

        delAndMoveTail(node);
        return node.value;


    }

    private void delAndMoveTail(DLinkedNode node) {
        delCurNode(node);
        moveTail(node);

        //TODO
        cache.put(node.key,node);

    }

    private void moveTail(DLinkedNode node) {
        //1.2.2、将该节点添加到末尾（末尾表示最近访问的）

        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }

    private  void delCurNode(DLinkedNode node) {
        //1.2存在
        //1.2.1、删除该节点
        node.pre.next = node.next;
        node.next.pre = node.pre;

    }

    public void put(int key, int value) {
        
        //1、在Map中快速查找这个key是否存在
        DLinkedNode node = cache.get(key);
        //1.1、存在跟新值，并且将这个节点添加到末尾，表示最近访问过
        if(node != null){
            node.value = value;
            delAndMoveTail(node);
            return;
        }



        //1.2、不存在
        //1.2.1、判断元素个数是否达到链表的最大容量
        DLinkedNode Dnode = new DLinkedNode(key, value);


        if(size >= capacity){
            //达到了最大容量，删除表头节点的下一个节点，将该节点添加到末尾
            //TODO，别忘了链表跟新之后跟新缓存
            DLinkedNode first = head.next;
            delCurNode(first);
            cache.remove(first.key);
            size--;
            moveTail(Dnode);
            size++;
            cache.put(key,Dnode);
        }else{
            //未达到最大容量，直接添加到链表的末尾
            moveTail(Dnode);
            size++;
            cache.put(key,Dnode);

        }
        

        


    }

    public static void main(String[] args) {

        LRUCache_146 lRUCache = new LRUCache_146(2);
        lRUCache.put(1, 1);
        lRUCache.put(2, 2);
        int i = lRUCache.get(1);
        lRUCache.put(3, 3);
        int i1 = lRUCache.get(2);
        lRUCache.put(4, 4);
        int i2 = lRUCache.get(1);
        int i3 = lRUCache.get(3);

        int i4 = lRUCache.get(4);

    }
}
